package com.hardy.leetcode;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;


/**
 * Created by 1340760685@qq.com on 2016/10/19. Given an array of strings, group anagrams together.
 *
 * For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:
 *
 * [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] Note: For the return value, each inner list's
 * elements must follow the lexicographic order. All inputs will be in lower-case.
 */
public class Anagrams {
    public static ArrayList<String> anagrams(String[] strs) {
        ArrayList<String> res=new ArrayList<String>();
        Map<String,ArrayList<String>> map=new HashMap<>();
        for(String s:strs){
            char[] temp=s.toCharArray();
            Arrays.sort(temp);
            String tempStr=new String(temp);
            if(map.containsKey(tempStr)){
               if(map.get(tempStr).size()==1){
                    res.add(map.get(tempStr).get(0));
                }
                map.get(tempStr).add(s);
                res.add(s);
            }else{
                ArrayList<String> tmpList=new ArrayList<>();
                tmpList.add(s);
                map.put(tempStr,tmpList);
            }
        }
        return res;
    }
    // [eat, tea, ate, tan, nat]
    public static void main(String[] args) {
        String[] str={"eat", "tea", "tan", "ate", "nat", "bat"};
        ArrayList<String> res=anagrams(str);
        System.out.println(res);
    }
}
